#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef int ElemType;

typedef struct STable
{
    ElemType *elem;
    int len;
} STable;

void InitSTable(STable &table, int len)
{
    table.elem = (ElemType *)malloc(sizeof(ElemType) * len);
    table.len = len;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        table.elem[i] = rand() % 100;
    }
}

void PrintSTable(STable table)
{
    for (int i = 0; i < table.len; i++)
    {
        printf("%3d", table.elem[i]);
    }
    printf("\n");
}

void Swap(ElemType &a, ElemType &b)
{
    ElemType t = a;
    a = b;
    b = t;
}

void BubbleSort(ElemType *elem, int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - i - 1; j++)
        {
            if (elem[j] > elem[j + 1])
            {
                Swap(elem[j], elem[j + 1]);
            }
        }
    }
}

void InsertSort(ElemType *elem, int len)
{
    for (int i = 1; i < len; i++)
    {
        int j;
        ElemType flag = elem[i];
        for (j = i - 1; j >= 0 && elem[j] > flag; j--)
        {
            elem[j + 1] = elem[j];
        }
        elem[j + 1] = flag;
    }
}

void SelectSort(ElemType *elem, int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        int min_index = i;
        for (int j = i + 1; j < len; j++)
        {
            if (elem[j] < elem[min_index])
            {
                min_index = j;
            }
        }
        Swap(elem[i], elem[min_index]);
    }
}

int main()
{
    STable table;
    InitSTable(table, 15);
    ElemType *new_elem;
    // memcpy(new_elem, table.elem, sizeof(ElemType) * table.len);
    PrintSTable(table);
    BubbleSort(table.elem, table.len);
    printf("----------------BubbleSort------------------\n");
    PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElemType) * table.len);
    PrintSTable(table);
    SelectSort(table.elem, table.len);
    printf("----------------SelectSort------------------\n");
    PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElemType) * table.len);
    PrintSTable(table);
    InsertSort(table.elem, table.len);
    printf("----------------InsertSort------------------\n");
    PrintSTable(table);

    PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    // MergeSort(table.elem, 0, table.len - 1);
    printf("----------------MergeSort------------------\n");
    PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    // QuickSort(table.elem, 0, table.len - 1);
    printf("----------------QuickSort------------------\n");
    PrintSTable(table);
    // memcpy(table.elem, new_elem, sizeof(ElementType) * table.len);
    PrintSTable(table);
    // HeapSort(table.elem, table.len);
    printf("----------------HeapSort------------------\n");
    PrintSTable(table);
    return 0;
}